Data expression using a list structure is a basic method in a software processing operation. FIGS. 25 to 28 illustrates diagrams of list structure control. FIG. 25 is a diagram of a one-way link list. FIG. 26 is a diagram of a two-way link list. Structures (or components) E1 to E3 in which data in a memory and link information are combined and are used to manage data for the list structure using software. As illustrated in FIGS. 25 and 26, main bodies of data (DATA) and pointers to next data (NEXT) indicating structures that are link destinations are defined in the structures E1 to E3. In the case of the one-way link list illustrated in FIG. 25, one pointer indicating the address of a subsequent structure is defined in a structure. In the case of the two-way link lists illustrated in FIGS. 26-28, two pointers indicating a subsequent structure (NEXT) and a precedent structure (PREVIOUS), respectively, are defined in a structure.
The list structure is a data structure that is effective in a case where a data sequence, namely, a permutation is meaningful and the insertion and removal of data is repeatedly performed. For example, when inserting data, pointers indicating structures E2 and E3 that are located anterior and posterior to data to be inserted and a pointer indicating structures E4 that corresponds to the data to be inserted are rewritten, as illustrated in FIG. 27. In addition, when removing data, only pointers of the structures E1 and E3 that are linked to the structure E2 to be removed are rewritten. FIG. 28 illustrates a removing operation that uses the link list.
In the link list method, have to be traced N−1 times from the top of a list in order to access the Nth component from the top. Therefore, the link list method takes time to search.
On the other hand, in order to perform similar operation as described above, an array structure can also be used. The array structure is a data structure that is effective in a case where a data sequence (a permutation) is meaningful and neither of the insertion nor the removal of data is performed. Unlike the list structure, the array structure is advantageous that each component can be accessed with one-time reference. Therefore, the array structure is effective when it is necessary to randomly access data. However, when the insertion of data is performed, all pieces of data located posterior to the insert position of data have to be copied one by one. In addition, when the removal of data is performed, all pieces of data located posterior to the remove position of data have to be copied one by one. Therefore, a processing time proportional to the number of components is necessary.
Accordingly, there is a trade-off relationship between the list structure and the array structure depending on the usage thereof. In addition, these structures are the bases of algorithm and a data structure on software, and hence several kinds of list structure processing operations performed on software have been proposed.
An example of documents that disclose a technique relating to link list control is Japanese Unexamined Patent Application Publication (Translation of PCT Application) No. 2008-530689.
In a list control operation that uses software, a large number of structures included in a list have to be rewritten when operating a data insertion operation and a data remove operation. Therefore, to perform these operations repeatedly, a long processing cycle is necessary. In addition, a processing time proportional to the scale of the list is necessary since the list has to be traced from the top thereof when the Nth component from the top of the list is checked.